#coding=utf-8

from random import randint

arr = [ randint(1,100) for i in range(11) ]
print("列表初始化:{}".format(arr))

def bubbled_sort(arr):
    '''冒泡排序
    1. 从第一个元素开始，比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。
    2. 对每一对相邻元素做同样的操作，从开始第一对到结尾的最后一对。这样在最后的元素应该是最大的数。
    3. 针对所有的元素重复以上的步骤，除了最后一个。
    4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
    '''
    arr_len = len(arr)
    for i in range(arr_len-1):
        # 内循环的范围:0 ~ arr_len-i-1
        for j in range(arr_len-i-1):
            if arr[j] >= arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

    return arr

def selected_sort(arr):
    '''选择排序
    1. 从第一个元素开始，假设该元素为最小值。
    2. 遍历未排序的元素，如果找到比当前最小值更小的元素，则更新最小值。
    3. 将最小值与第一个元素交换位置。
    4. 重复步骤1-3,直到所有元素都排序完成
    '''
    arr_len = len(arr)
    for i in range(arr_len):
        min_idx = i
        for j in range(i, arr_len):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # min_idx != i，完成元素值交换           
        if min_idx != i:
            arr[min_idx] , arr[i] = arr[i], arr[min_idx]
    
    return arr

def inserted_sort(arr):
    '''插入排序 - 不太理解
    1. 从第一个元素开始，该元素可以认为已经被排序。
    2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
    3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
    4. 重复步骤3,直到找到已排序的元素小于或等于新元素的位置。
    5. 将新元素插入到该位置后。
    6. 重复步骤2~5。
    '''
    arr_len = len(arr)
    for i in range(1, arr_len):
        tmp = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > tmp:
            arr[j+1] = arr[j]
            j -=1
        arr[j+1] = tmp
   
    return arr        

def quick_sort(arr):
    '''快速排序
    1. 选择一个元素作为"基准"，通常选择第一个元素或者最后一个元素。
    2. 重新排列数组，所有比"基准"小的元素摆放在"基准"前面，所有比"基准"大的元素摆在"基准"后面（相同的数可以到任一边）。在这个分区退出之后，该"基准"就处于数列的中间位置。这个称为分区(partition)操作。
    3. 递归地(recursive)把小于"基准"元素的子数列和大于"基准"元素的子数列排序
    '''
    arr_len = len(arr)
    if arr_len <= 1:
        return arr
    povit = arr[arr_len//2]
    left_arr = [item  for item in arr if item < povit]
    mid_arr = [item  for item in arr if item == povit]
    right_arr = [item  for item in arr if item > povit]
    return quick_sort(left_arr) + mid_arr + quick_sort(right_arr)

def merge(left, right):
    '''归并排序之合并函数
    '''
    result = []
    i, j = 0,0
    left_len = len(left)
    right_len = len(right)
    while i < left_len and j < right_len:
        if left[i] <= right[j]:
            result.append(left[i])
            i +=1
        else:
            result.append(right[j])
            j+=1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
    
def merge_sort(arr):
    '''归并排序
    1. 分解:将待排序的n个元素的序列看作n个长度为1的有序子序列。
    2. 合并:依次将相邻的有序子序列两两合并, 得到n/2个长度为2或1的有序子序列。
    3. 再合并:再将这些有序子序列两两合并, 如此重复, 直到得到一个有序序列为止
    '''
    arr_len = len(arr)
    if arr_len<=1:
        return arr
    mid = arr_len // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    return merge(left_arr, right_arr)

if __name__ == "__main__":
    print("冒泡排序结果:{}".format(bubbled_sort(arr)))
    print("选择排序结果:{}".format(selected_sort(arr)))
    print("插入排序结果:{}".format(inserted_sort(arr))) 
    print("快速排序结果:{}".format(quick_sort(arr)))
    print("归并排序结果:{}".format(merge_sort(arr)))
